function swap(arr, i, j) {
    let t = arr[i];
    arr[i] = arr[j];
    arr[j] = t;
}
/**
 * 1.颜色分类
 * 给定一个包含红色、白色和蓝色，一共 n 个元素的数组，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
 * 此题中，我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
 * @param {number[]} nums
 * @return {void} Do not return anything, modify nums in-place instead.
 */
var sortColors = function(nums) {
    let p0 = 0,
        p2 = nums.length - 1,
        i = 0;
    while (i <= p2) {
        while (i < p2 && nums[i] === 2) {
            swap(nums, i, p2);
            --p2;
        }
        if (nums[i] === 0) {
            swap(nums, i, p0);
            ++p0;
        }
        ++i;
    }
    // let p0 = p1 = 0;
    // for (let i = 0; i < nums.length; i++) {
    //     const item = nums[i];
    //     if (item === 0) {
    //         swap(nums, i, p0);
    //         if (p1 > p0) {
    //             swap(nums, i, p1);
    //         }
    //         p0++;
    //         p1++;
    //     } else if (item === 1) {
    //         swap(nums, i, p1);
    //         p1++;
    //     }
    // }
    return nums;
};
// console.log('sortColors:', sortColors([2,0,2,1,1,0]));
/**
 * 2.前 K 个高频元素
 * 给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var topKFrequent = function(nums, k) {
    let map = new Map();
    for (const item of nums) {
        if (map.has(item)) {
            map.set(item, map.get(item) + 1);
        } else {
            map.set(item, 1);
        }
    }
    // 稀疏列表
    // let arr = [];
    // for (const [key, val] of map) {
    //     let elems = arr[val] ? arr[val] : (arr[val] = []);
    //     elems.push(key);
    // }
    // let res = [];
    // while (arr.length && k) {
    //     let elems = arr.pop();
    //     if (elems) {
    //         while (elems.length && k--) {
    //             res.push(elems.pop());
    //         }
    //     }
    // }
    // return res;

    // 堆排:小顶堆
    let heap = [];
    for (const item of map) {
        if (heap.length < k) {
            let len = heap.push(item);
            if (len === k) {
                let border = Math.floor((k - 1) / 2);
                for (let i = border; i >= 0; i--) {
                    resetHeap(heap, i, k);
                }
            }
        } else {
            let least = heap[0];
            if (least[1] < item[1]) {
                heap[0] = item;
                resetHeap(heap, 0, k);
            }
        }
    }
    return heap.map(item => item[0]);
};
function resetHeap(arr, index, max) {
    let left = index * 2 + 1,
        right = index * 2 + 2,
        least = index;
    if (left < max && arr[least][1] > arr[left][1]) {
        least = left;
    }
    if (right < max && arr[least][1] > arr[right][1]) {
        least = right;
    }
    if (least !== index) {
        swap(arr, index, least);
        resetHeap(arr, least, max);
    }
}
// console.log('topKFrequent:', topKFrequent([5,2,5,3,5,3,1,1,3], 2));
// console.log('topKFrequent:', topKFrequent([6,0,1,4,9,7,-3,1,-4,-8,4,-7,-3,3,2,-3,9,5,-4,0], 6));
/**
 * 3.数组中的第K个最大元素
 * 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
 * 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var findKthLargest = function(nums, k) {
    // 小顶堆
    let heap = nums.slice(0, k);
    for (let i = Math.floor((k - 2) / 2); i >= 0; i--) {
        resetHeap2(heap, i, k);
    }
    for (let i = k; i < nums.length; i++) {
        if (nums[i] > heap[0]) {
            heap[0] = nums[i];
            resetHeap2(heap, 0, k);
        }
    }
    return heap[0];
};
function resetHeap2(arr, index, max) {
    let left = index * 2 + 1,
        right = index * 2 + 2,
        least = index;
    if (left < max && arr[least] > arr[left]) {
        least = left;
    }
    if (right < max && arr[least] > arr[right]) {
        least = right;
    }
    if (least !== index) {
        swap(arr, index, least);
        resetHeap2(arr, least, max);
    }
}
// console.log('findKthLargest:', findKthLargest([3,2,3,1,2,4,5,5,6], 6));
/**
 * 3.寻找峰值
 * 峰值元素是指其值大于左右相邻值的元素。
 * 给你一个输入数组 nums，找到峰值元素并返回其索引。数组可能包含多个峰值，在这种情况下，返回 任何一个峰值 所在位置即可。
 * 你可以假设 nums[-1] = nums[n] = -∞ 。
 * @param {number[]} nums nums[i] != nums[i + 1]
 * @return {number}
 */
var findPeakElement = function(nums) {
    // 线性查找
    // for (let i = 0; i < nums.length - 1; i++) {
    //     if (nums[i] > nums[i + 1]) {
    //         return i;
    //     }
    // }
    // return nums.length - 1;
    // 二分查找
    let high = nums.length - 1,
        low = 0;
    while (low < high) {
        let mid = Math.floor((high + low) / 2);
        if (nums[mid] > nums[mid + 1]) {
            high = mid;
        } else {
            low = mid + 1;
        }
    }
    return low;
};
// console.log('findPeakElement:', findPeakElement([1,2,4,3]));
/**
 * 4.在排序数组中查找元素的第一个和最后一个位置
 * 给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
 * 如果数组中不存在目标值 target，返回 [-1, -1]。
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var searchRange = function(nums, target) {
    let l = 0,
        r = nums.length - 1;
    let res = [-1, -1];
    while (l <= r) {
        let mid = Math.floor((l + r) / 2);
        if (nums[mid] < target) {
            l = mid + 1;
        } else if (nums[mid] > target) {
            r = mid - 1
        } else { // nums[mid] === target
            if (nums[l] !== target) {
                ++l;
            } else {
                res[0] = l;
            }
            if (nums[r] !== target) {
                --r;
            } else {
                res[1] = r;
            }
            if (!res.includes(-1)) {
                break;
            }
        }
    }
    return res;
};
// console.log('searchRange:', searchRange([5,7,7,8,8,10], 7));
/**
 * 5.合并区间
 * 以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。
 * 请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。
 * @param {number[][]} intervals
 * @return {number[][]}
 */
var merge = function(intervals) {
    quickSort(intervals);
    let res = [];
    let len = intervals.length;
    for (let i = 0; i < len; i++) {
        let [start, end] = intervals[i];
        let j = i + 1;
        let section = [start, end];
        while (j < len) {
            let node = intervals[j];
            if (end >= node[0]) {
                end = end > node[1] ? end : node[1];
                section[1] = end;
                ++j;
            } else {
                break;
            }
        }
        res.push(section);
        i = j - 1;
    }
    return res;
};
function quickSort(arr, l, r) {
    isFinite(l) || (l = 0);
    isFinite(r) || (r = arr.length - 1);
    if (l >= r) {
        return;
    }
    let ltI = l,
        m = arr[l];
    for (let i = l + 1; i <= r; i++) {
        if (arr[i][0] < m[0]) {
            swap(arr, i, ++ltI);
        }
    }
    swap(arr, l, ltI);
    quickSort(arr, l, ltI - 1);
    quickSort(arr, ltI + 1, r);
}
// console.log('merge:', merge([[1,3],[15,18],[2,6],[8,10]]));
// console.log('merge:', merge([[1,4],[4,5]]));
// console.log('merge:', merge([[2,3],[2,2],[3,3],[1,3],[5,7],[2,2],[4,6]]));
/**
 * 6.搜索旋转排序数组
 * 整数数组 nums 按升序排列，数组中的值 互不相同 。
 * 在传递给函数之前，nums 在预先未知的某个下标 k（0 <= k < nums.length）上进行了 旋转，
 * 使数组变为 [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]]（下标 从 0 开始 计数）。
 * 例如， [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
 * 给你 旋转后 的数组 nums 和一个整数 target ，如果 nums 中存在这个目标值 target ，则返回它的下标，否则返回 -1 。
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var search = function(nums, target) {
    let upper = nums.length - 1;
    if (nums[upper] === target) {
        return upper;
    }
    let i;
    if (nums[upper] < target) {
        i = 0;
        while (i < upper && nums[i] <= nums[i + 1] && nums[i] < target) {
            ++i;
        }  
    } else {
        i = upper;
        while (i > 0 && nums[i] >= nums[i - 1] && nums[i] > target) {
            --i;
        }
    }
    if (nums[i] === target) {
        return i;
    }
    return -1;
};
// console.log('search:', search([4,5,6,7,0,1,2], 4));
// console.log('search:', search([4,5,6,7,0,1,2], 5));
// console.log('search:', search([1], 0));
/**
 * 7.搜索二维矩阵 II
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：
 *  · 每行的元素从左到右升序排列。
 *  · 每列的元素从上到下升序排列。
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var searchMatrix = function(matrix, target) {
    let rows = matrix.length,
        cols = matrix[0].length,
        rl = rows - 1,
        cl = cols - 1,
        i = j = 0;
    if (matrix[i][j] > target) {
        return false;
    }
    while (matrix[i][j] < target) {
        // 边界值处理
        if (i === rl && j === cl) {
            return false;
        }
        (i < rl) && ++i;
        (j < cl) && ++j;
    }
    if (matrix[i][j] === target) {
        return true;
    }
    if (binarySearch(matrix, target, 0, j, i - 1, cl)) {
        return true;
    };
    if (binarySearch(matrix, target, i, 0, rl, j - 1)) {
        return true;
    }
    return false;
};
function binarySearch(matrix, target, startR, startC, endR, endC) {
    let i = startR;
    while (i <= endR) {
        let j = startC;
        while (j <= endC) {
            if (matrix[i][j] === target) {
                return true;
            }
            if (matrix[i][j] > target) {
                break;
            }
            ++j;
        }
        ++i;
    }
    return false;
}
// console.log('searchMatrix:', searchMatrix([[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]], 30)); // true
// console.log('searchMatrix:', searchMatrix([[-5]], -10)); // false
// console.log('searchMatrix:', searchMatrix([[-1,3]], 1)); // false
// console.log('searchMatrix:', searchMatrix([
//     [1,2,3,4,5],
//     [6,7,8,9,10],
//     [11,12,13,14,15],
//     [16,17,18,19,20],
//     [21,22,23,24,25]
// ], 15)); // true
// console.log('searchMatrix:', searchMatrix([
//     [3,3,8,13,13,18],
//     [4,5,11,13,18,20],
//     [9,9,14,15,23,23],
//     [13,18,22,22,25,27],
//     [18,22,23,28,30,33],
//     [21,25,28,30,35,35],
//     [24,25,33,36,37,40]
// ], 21)); // true

// function quickSort(nums) {
//     function dp(arr, low, high) {
//         if (low >= high) {
//             return;
//         }
//         let m = arr[low];
//         let p = low;
//         for (let i = low + 1; i <= high; i++) {
//             if (arr[i] < m) {
//                 swap(arr, i, ++p);
//             }
//         }
//         swap(arr, p, low);
//         dp(arr, low, p - 1);
//         dp(arr, p + 1, high);
//         return nums;
//     }
//     return dp(nums, 0, nums.length - 1);
// }
// console.log(quickSort([6,5,7,3,1,4,2,0]));
